package com.platform.modules.alg.alglib.poj1743;

public class Poj1743 {
    public String output = "";

    private int maxn = 20010;
    private int maxm = maxm = 200;
    int n;
    int k; // 重复 k 次

    int s[] = new int[maxn];
    int ss[] = new int[maxn];
    int sa[] = new int[maxn];
    // 名称数组
    int rank[] = new int[maxn];
    // 高度数组
    int height[] = new int[maxn];
    int wa[] = new int[maxn];
    int wb[] = new int[maxn];
    int wv[] = new int[maxn];
    // c[]用于基数排序统计
    int c[] = new int[maxm];

    boolean cmp(int r[], int a, int b, int l) {
        return (r[a] == r[b]) && (r[a + l] == r[b + l]);
    }

    // 交换两个数组的内容 https://blog.csdn.net/m0_56793367/article/details/115599564
    public static void swap(int[] array1, int[] array2) {
        int tmp = 0;
        for (int i = 0; i < array1.length; i++) {
            tmp = array1[i];
            array1[i] = array2[i];
            array2[i] = tmp;
        }
    }

    void da(int r[], int sa[], int n, int m) {
        int i, k, p;
        int x[] = wa;
        int y[] = wb;
        for (i = 0; i < m; i++) // 基数排序
            c[i] = 0;
        for (i = 0; i < n; i++)
            c[x[i] = r[i]]++;
        for (i = 1; i < m; i++)
            c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[--c[x[i]]] = i;
        for (k = 1; k <= n; k <<= 1) {
            // 直接利用 sa 排序第二关键字
            p = 0;
            for (i = n - k; i < n; i++)
                y[p++] = i; // 补零的位置下标排在最前面
            for (i = 0; i < n; i++)
                if (sa[i] >= k)
                    y[p++] = sa[i] - k;
            // 基数排序第一关键字
            for (i = 0; i < n; i++)
                wv[i] = x[y[i]]; // 将第二关键字排序结果转换为名次，进行排序
            for (i = 0; i < m; i++)
                c[i] = 0;
            for (i = 0; i < n; i++)
                c[wv[i]]++;
            for (i = 1; i < m; i++)
                c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i--)
                sa[--c[wv[i]]] = y[i];
            // 根据 sa 和 x 数组，重新计算新的x数组
            swap(x, y); // y 数组已经没有用，更新x需要使用x本身数据，因此放入y使用
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
            if (p >= n)//排序结束
                break;
            m = p;
        }
    }

    void calheight(int r[], int sa[], int n) {
        int i, j, k = 0;
        for (i = 1; i <= n; i++)
            rank[sa[i]] = i;
        for (i = 0; i < n; i++) {
            if (k > 0)
                k--;
            j = sa[rank[i] - 1];
            while (r[i + k] == r[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

    boolean check(int mid) {
        int mx = sa[1], mn = sa[1];
        for (int i = 2; i <= n; i++) {
            if (height[i] >= mid) {
                mx = Math.max(mx, sa[i]);
                mn = Math.min(mn, sa[i]);
                if (mx - mn >= mid)
                    return true;
            } else {
                mx = sa[i];
                mn = sa[i];
            }
        }
        return false;
    }

    void solve() {
        int L = 4, R = n, res = -1; // 答案必须>=4
        while (L <= R) {
            int mid = (L + R) >> 1;
            if (check(mid)) {
                res = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }
        if (res < 4)
            output += "0\n";
        else
            output += res + 1 + "\n";
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        String[] num = line[1].split(" ");

        for (int i = 0; i < n; i++)
            s[i] = Integer.parseInt(num[i]);
        if (n < 9) {
            output += "0\n";
        }
        n--;
        for (int i = 0; i < n; i++)
            ss[i] = this.s[i + 1] - this.s[i] + 100;
        ss[n] = 0;
        da(ss, sa, n + 1, 200);
        calheight(ss, sa, n);
        solve();
        return output;
    }
}
